home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / xlib / xlib06p2 / dipoly.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-09  |  12.1 KB  |  286 lines
  1. /* Color-fills a convex polygon. All vertices are offset by (XOffset,
  2.    YOffset). "Convex" means that every horizontal line drawn through
  3.    the polygon at any vertex would cross exactly two active edges
  4.    (neither horizontal lines nor zero-length edges count as active
  5.    edges; both are acceptable anywhere in the polygon), and that the
  6.    right & left edges never cross. (It's OK for them to touch, though,
  7.    so long as the right edge never crosses over to the left of the
  8.    left edge.) Nonconvex polygons won't be drawn properly. Returns 1
  9.    for success, 0 if memory allocation failed.
  10.  
  11.    Compiled with Borland C++ 4.02.  Link with L21-3.C.
  12.    Checked by Jim Mischel 11/30/94.
  13.  */
  14.  
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include "dipoly.h"
  18.  
  19. /* Advances the index by one vertex forward through the vertex list,
  20.    wrapping at the end of the list */
  21. #define INDEX_FORWARD(Index) \
  22.    Index = (Index + 1) % VertexList->iLength;
  23.  
  24. /* Advances the index by one vertex backward through the vertex list,
  25.    wrapping at the start of the list */
  26. #define INDEX_BACKWARD(Index) \
  27.    Index = (Index - 1 + VertexList->iLength) % VertexList->iLength;
  28.  
  29. /* Advances the index by one vertex either forward or backward through
  30.    the vertex list, wrapping at either end of the list */
  31. #define INDEX_MOVE(Index,Direction)                                  \
  32.    if (Direction > 0)                                                \
  33.       Index = (Index + 1) % VertexList->iLength;                      \
  34.    else                                                              \
  35.       Index = (Index - 1 + VertexList->iLength) % VertexList->iLength;
  36.  
  37. void ScanEdge(int, int, int, int, int, int, struct hLine **);
  38.  
  39. hLineList * phllScannedPolygon(
  40.         struct vertexListHeader * VertexList,
  41.   int XOffset,
  42.         int YOffset
  43. )
  44. {
  45.   int i, MinIndexL, MaxIndex, MinIndexR, SkipFirst, Temp;
  46.   int MinPoint_Y, MaxPoint_Y, TopIsFlat, LeftEdgeDir;
  47.   int NextIndex, CurrentIndex, PreviousIndex;
  48.   int DeltaXN, DeltaYN, DeltaXP, DeltaYP;
  49.   static struct hLineList hllWorking;
  50.   struct hLine *EdgePointPtr;
  51.   struct vertex *VertexPtr;
  52.  
  53.   /* Point to the vertex list */
  54.   VertexPtr = VertexList->pvtx;
  55.  
  56.   /* Scan the list to find the top and bottom of the polygon */
  57.   if (VertexList->iLength == 0) {
  58.     return NULL;
  59.         }
  60.   MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndexL = MaxIndex = 0].iY;
  61.   for (i = 1; i < VertexList->iLength; i++) {
  62.     if (VertexPtr[i].iY < MinPoint_Y) {
  63.       MinPoint_Y = VertexPtr[MinIndexL = i].iY; /* new top */
  64.     }
  65.     else if (VertexPtr[i].iY > MaxPoint_Y) {
  66.       MaxPoint_Y = VertexPtr[MaxIndex = i].iY; /* new bottom */
  67.     }
  68.   }
  69.   if (MinPoint_Y == MaxPoint_Y) {
  70.     return NULL;
  71.   }
  72.  
  73.   // Scan in ascending order to find the last top-edge point
  74.   MinIndexR = MinIndexL;
  75.   while (VertexPtr[MinIndexR].iY == MinPoint_Y)
  76.     INDEX_FORWARD(MinIndexR);
  77.   INDEX_BACKWARD(MinIndexR); //back up to last top-edge point
  78.  
  79.   // Now scan in descending order to find the first top-edge point
  80.   while (VertexPtr[MinIndexL].iY == MinPoint_Y)
  81.     INDEX_BACKWARD(MinIndexL);
  82.   INDEX_FORWARD(MinIndexL); // back up to first top-edge point
  83.  
  84.   // Figure out which direction through the vertex list from the top
  85.   //   vertex is the left edge and which is the right
  86.   LeftEdgeDir = -1; // assume left edge runs down thru vertex list
  87.   if ((TopIsFlat = (VertexPtr[MinIndexL].iX !=
  88.         VertexPtr[MinIndexR].iX) ? 1 : 0) == 1) {
  89.      /* If the top is flat, just see which of the ends is leftmost */
  90.      if (VertexPtr[MinIndexL].iX > VertexPtr[MinIndexR].iX) {
  91.         LeftEdgeDir = 1;  /* left edge runs up through vertex list */
  92.         Temp = MinIndexL;       /* swap the indices so MinIndexL   */
  93.         MinIndexL = MinIndexR;  /* points to the start of the left */
  94.         MinIndexR = Temp;       /* edge, similarly for MinIndexR   */
  95.      }
  96.   } else {
  97.      /* Point to the downward end of the first line of each of the
  98.         two edges down from the top */
  99.      NextIndex = MinIndexR;
  100.      INDEX_FORWARD(NextIndex);
  101.      PreviousIndex = MinIndexL;
  102.      INDEX_BACKWARD(PreviousIndex);
  103.      /* Calculate X and Y lengths from the top vertex to the end of
  104.         the first line down each edge; use those to compare slopes
  105.         and see which line is leftmost */
  106.      DeltaXN = VertexPtr[NextIndex].iX - VertexPtr[MinIndexL].iX;
  107.      DeltaYN = VertexPtr[NextIndex].iY - VertexPtr[MinIndexL].iY;
  108.      DeltaXP = VertexPtr[PreviousIndex].iX - VertexPtr[MinIndexL].iX;
  109.      DeltaYP = VertexPtr[PreviousIndex].iY - VertexPtr[MinIndexL].iY;
  110.      if (((long)DeltaXN * DeltaYP - (long)DeltaYN * DeltaXP) < 0L) {
  111.         LeftEdgeDir = 1;  /* left edge runs up through vertex list */
  112.         Temp = MinIndexL;       /* swap the indices so MinIndexL   */
  113.         MinIndexL = MinIndexR;  /* points to the start of the left */
  114.         MinIndexR = Temp;       /* edge, similarly for MinIndexR   */
  115.      }
  116.   }
  117.  
  118.   /* Set the # of scan lines in the polygon, skipping the bottom edge
  119.      and also skipping the top vertex if the top isn't flat because
  120.      in that case the top vertex has a right edge component, and set
  121.      the top scan line to draw, which is likewise the second line of
  122.      the polygon unless the top is flat */
  123.   if ((hllWorking.iLength = MaxPoint_Y - MinPoint_Y - 1 + TopIsFlat) <= 0) {
  124.     return NULL;
  125.   }
  126.   hllWorking.iYStart = YOffset + MinPoint_Y + 1 - TopIsFlat;
  127.  
  128.   /* Get memory in which to store the line list we generate */
  129.   if ((hllWorking.phln = new hLine[ hllWorking.iLength ]) == NULL) {
  130.      return( NULL);  /* couldn't get memory for the line list */
  131.   }
  132.  
  133.   /* Scan the left edge and store the boundary points in the list */
  134.   /* Initial pointer for storing scan converted left-edge coords */
  135.   EdgePointPtr = hllWorking.phln;
  136.   /* Start from the top of the left edge */
  137.   PreviousIndex = CurrentIndex = MinIndexL;
  138.   /* Skip the first point of the first line unless the top is flat;
  139.      if the top isn't flat, the top vertex is exactly on a right
  140.      edge and isn't drawn */
  141.   SkipFirst = TopIsFlat ? 0 : 1;
  142.   /* Scan convert each line in the left edge from top to bottom */
  143.   do {
  144.     INDEX_MOVE(CurrentIndex,LeftEdgeDir);
  145.     ScanEdge(VertexPtr[PreviousIndex].iX + XOffset,
  146.       VertexPtr[PreviousIndex].iY,
  147.       VertexPtr[CurrentIndex].iX + XOffset,
  148.       VertexPtr[CurrentIndex].iY, 1, SkipFirst, &EdgePointPtr);
  149.     PreviousIndex = CurrentIndex;
  150.     SkipFirst = 0; /* scan convert the first point from now on */
  151.   } while (CurrentIndex != MaxIndex);
  152.  
  153.   /* Scan the right edge and store the boundary points in the list */
  154.   EdgePointPtr = hllWorking.phln;
  155.   PreviousIndex = CurrentIndex = MinIndexR;
  156.   SkipFirst = TopIsFlat ? 0 : 1;
  157.   /* Scan convert the right edge, top to bottom. X coordinates are
  158.      adjusted 1 to the left, effectively causing scan conversion of
  159.      the nearest points to the left of but not exactly on the edge */
  160.   do {
  161.     INDEX_MOVE(CurrentIndex,-LeftEdgeDir);
  162.     ScanEdge(VertexPtr[PreviousIndex].iX + XOffset - 1,
  163.       VertexPtr[PreviousIndex].iY,
  164.       VertexPtr[CurrentIndex].iX + XOffset - 1,
  165.       VertexPtr[CurrentIndex].iY, 0, SkipFirst, &EdgePointPtr);
  166.     PreviousIndex = CurrentIndex;
  167.     SkipFirst = 0; /* scan convert the first point from now on */
  168.   } while (CurrentIndex != MaxIndex);
  169.  
  170.   return &hllWorking;
  171. }
  172.  
  173.  
  174. void ScanEdge(
  175.         int X1,
  176.         int Y1,
  177.         int X2,
  178.         int Y2,
  179.         int SetXStart,
  180.   int SkipFirst,
  181.         struct hLine **EdgePointPtr
  182. )
  183. {
  184.    int DeltaX, Height, Width, AdvanceAmt, ErrorTerm, i;
  185.    int ErrorTermAdvance, XMajorAdvanceAmt;
  186.    struct hLine *WorkingEdgePointPtr;
  187.  
  188.    WorkingEdgePointPtr = *EdgePointPtr; /* avoid double dereference */
  189.    AdvanceAmt = ((DeltaX = X2 - X1) > 0) ? 1 : -1;
  190.                             /* direction in which X moves (Y2 is
  191.                                always > Y1, so Y always counts up) */
  192.  
  193.    if ((Height = Y2 - Y1) <= 0)  /* Y length of the edge */
  194.       return;     /* guard against 0-length and horizontal edges */
  195.  
  196.    /* Figure out whether the edge is vertical, diagonal, X-major
  197.       (mostly horizontal), or Y-major (mostly vertical) and handle
  198.       appropriately */
  199.    if ((Width = abs(DeltaX)) == 0) {
  200.       /* The edge is vertical; special-case by just storing the same
  201.          X coordinate for every scan line */
  202.       /* Scan the edge for each scan line in turn */
  203.       for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
  204.          /* Store the X coordinate in the appropriate edge list */
  205.          if (SetXStart == 1)
  206.             WorkingEdgePointPtr->iXStart = X1;
  207.          else
  208.             WorkingEdgePointPtr->iXEnd = X1;
  209.       }
  210.    } else if (Width == Height) {
  211.       /* The edge is diagonal; special-case by advancing the X
  212.          coordinate 1 pixel for each scan line */
  213.       if (SkipFirst) /* skip the first point if so indicated */
  214.          X1 += AdvanceAmt; /* move 1 pixel to the left or right */
  215.       /* Scan the edge for each scan line in turn */
  216.       for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
  217.          /* Store the X coordinate in the appropriate edge list */
  218.          if (SetXStart == 1)
  219.             WorkingEdgePointPtr->iXStart = X1;
  220.          else
  221.             WorkingEdgePointPtr->iXEnd = X1;
  222.          X1 += AdvanceAmt; /* move 1 pixel to the left or right */
  223.       }
  224.    } else if (Height > Width) {
  225.       /* Edge is closer to vertical than horizontal (Y-major) */
  226.       if (DeltaX >= 0)
  227.          ErrorTerm = 0; /* initial error term going left->right */
  228.       else
  229.          ErrorTerm = -Height + 1;   /* going right->left */
  230.       if (SkipFirst) {   /* skip the first point if so indicated */
  231.          /* Determine whether it's time for the X coord to advance */
  232.          if ((ErrorTerm += Width) > 0) {
  233.             X1 += AdvanceAmt; /* move 1 pixel to the left or right */
  234.             ErrorTerm -= Height; /* advance ErrorTerm to next point */
  235.          }
  236.       }
  237.       /* Scan the edge for each scan line in turn */
  238.       for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
  239.          /* Store the X coordinate in the appropriate edge list */
  240.          if (SetXStart == 1)
  241.             WorkingEdgePointPtr->iXStart = X1;
  242.          else
  243.             WorkingEdgePointPtr->iXEnd = X1;
  244.          /* Determine whether it's time for the X coord to advance */
  245.          if ((ErrorTerm += Width) > 0) {
  246.             X1 += AdvanceAmt; /* move 1 pixel to the left or right */
  247.             ErrorTerm -= Height; /* advance ErrorTerm to correspond */
  248.          }
  249.       }
  250.    } else {
  251.       /* Edge is closer to horizontal than vertical (X-major) */
  252.       /* Minimum distance to advance X each time */
  253.       XMajorAdvanceAmt = (Width / Height) * AdvanceAmt;
  254.       /* Error term advance for deciding when to advance X 1 extra */
  255.       ErrorTermAdvance = Width % Height;
  256.       if (DeltaX >= 0)
  257.          ErrorTerm = 0; /* initial error term going left->right */
  258.       else
  259.          ErrorTerm = -Height + 1;   /* going right->left */
  260.       if (SkipFirst) {   /* skip the first point if so indicated */
  261.          X1 += XMajorAdvanceAmt;    /* move X minimum distance */
  262.          /* Determine whether it's time for X to advance one extra */
  263.          if ((ErrorTerm += ErrorTermAdvance) > 0) {
  264.             X1 += AdvanceAmt;       /* move X one more */
  265.             ErrorTerm -= Height; /* advance ErrorTerm to correspond */
  266.          }
  267.       }
  268.       /* Scan the edge for each scan line in turn */
  269.       for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
  270.          /* Store the X coordinate in the appropriate edge list */
  271.          if (SetXStart == 1)
  272.             WorkingEdgePointPtr->iXStart = X1;
  273.          else
  274.             WorkingEdgePointPtr->iXEnd = X1;
  275.          X1 += XMajorAdvanceAmt;    /* move X minimum distance */
  276.          /* Determine whether it's time for X to advance one extra */
  277.          if ((ErrorTerm += ErrorTermAdvance) > 0) {
  278.             X1 += AdvanceAmt;       /* move X one more */
  279.             ErrorTerm -= Height; /* advance ErrorTerm to correspond */
  280.          }
  281.       }
  282.    }
  283.  
  284.    *EdgePointPtr = WorkingEdgePointPtr;   /* advance caller's ptr */
  285. }
  286.